#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        unordered_set<string> bankSet(bank.begin(), bank.end());
        if (!bankSet.count(end)) return -1;
        vector<char> choices = { 'A', 'C', 'G', 'T' };
        unordered_set<string> visited;
        queue<string> q;
        q.push(start);
        visited.insert(start);
        int steps = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                string curr = q.front();
                q.pop();
                if (curr == end) return steps;
                for (int j = 0; j < 8; j++) {
                    char original = curr[j];
                    for (char ch : choices) {
                        if (ch == original) continue;
                        curr[j] = ch;
                        if (bankSet.count(curr) && !visited.count(curr)) {
                            visited.insert(curr);
                            q.push(curr);
                        }
                    }
                    curr[j] = original;
                }
            }
            steps++;
        }

        return -1;
    }
};